/*
leetcode 20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    每个右括号都有一个对应的相同类型的左括号。
 
示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([])"
输出：true

提示：
1 <= s.length <= 10^4
s 仅由括号 '()[]{}' 组成
*/
#include <iostream>
#include <stack>
#include <unordered_map>
#include <string>

using namespace std;

bool isValid(string s) {
    // 用栈保存未匹配的左括号
    stack<char> st;

    // 使用哈希表存储括号的映射关系
    //键（Key）：右括号，包括 ')'、']' 和 '}'。
    //值（Value）：对应的左括号，包括 '('、'[' 和 '{'。

    unordered_map<char, char> brackets = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };

    for (char c : s) {

        // 如果是右括号
        //在 unordered_map 中，count(key) 用于检查给定的 键key 是否存在于哈希表中
        //如果 key 存在，返回 1. 如果 键key 不存在，返回 0
        if (brackets.count(c)) {

            // 栈顶字符与右括号的匹配
            //检查栈是否为空，或者栈顶是否与当前右括号的匹配左括号相同
            //通过 brackets[c] 找到右括号对应的左括号，如果 c 是 ')'，brackets[c] 就是 '('。
            if (!st.empty() && st.top() == brackets[c]) {

                st.pop(); // 匹配成功，移除栈顶
            } 
            else {
                return false; // 匹配失败
            }
        } 
        else {
            // 如果是左括号，入栈
            st.push(c);
        }
    }

    // 栈为空表示所有括号都匹配成功
    return st.empty();
}

int main() {
    string s = "{[()]}";
    if (isValid(s)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    return 0;
}

/*
栈（stack）：
    栈是一种后进先出（LIFO）的数据结构，适合处理括号匹配的问题。
    每当遇到左括号时，将其压入栈中。
    每当遇到右括号时，检查栈顶是否为匹配的左括号。

以输入 s = "{[()]}" 为例：

遍历字符 '{'：入栈 st = ['{']。
遍历字符 '['：入栈 st = ['{', '[']。
遍历字符 '('：入栈 st = ['{', '[', '(']。
遍历字符 ')'：
栈顶为 '('，匹配成功，弹出栈顶 st = ['{', '[']。
遍历字符 ']'：
栈顶为 '['，匹配成功，弹出栈顶 st = ['{']。
遍历字符 '}'：
栈顶为 '{'，匹配成功，弹出栈顶 st = []。
遍历结束，栈为空，返回 true。
*/
